In this paper, by constructing extremely hard examples of CSP (with large domains) and SAT (with long clauses), we prove that such examples cannot be solved without exhaustive search, which is stronger than P $\neq$ NP. This constructive approach for proving impossibility results is very different (and missing) from those currently used in computational complexity theory, but is similar to that used by Kurt G\"{o}del in proving his famous logical impossibility results. Just as shown by G\"{o}del's results that proving formal unprovability is feasible in mathematics, the results of this paper show that proving computational hardness is not hard in mathematics. Specifically, proving lower bounds for many problems, such as 3-SAT, can be challenging because these problems have various effective strategies available for avoiding exhaustive search. However, in cases of extremely hard examples, exhaustive search may be the only viable option, and proving its necessity becomes more straightforward. Consequently, it makes the separation between SAT (with long clauses) and 3-SAT much easier than that between 3-SAT and 2-SAT. Finally, the main results of this paper demonstrate that the fundamental difference between the syntax and the semantics revealed by G\"{o}del's results also exists in CSP and SAT.

In many combinatorial optimization and decision problems, what people concern is to find solutions of minimal costs. In practice, however, such optimal solutions can be very brittle in that if the value of one variable becomes unavailable, repairing this solution leads to a great increase in its final cost. Therefore, the concept of super solution is introduced to formalize a solution with a certain degree of robustness or stability. To quantify the robustness, (a, b)-super solution was introduced to constraint programming in [3]. Specifically, an (a,b)-super solution is one in which if the values assigned to a variables are no longer available, the solution can be repaired by assigning these variables withanew values and at most b other variables. Over the past years, random models of constraint satisfaction problems (CSPs) have been intensively studied. Initially, four "standard" models known as models A, B, C and D [4, 2] have been introduced to generate random binary CSP instances.

The study of random constraint satisfaction problems (CSPs) has received tremendous ideas from combinatorics, computer science and statistical physics. Random CSPs contain a large set of variables which interact through a large set of constraints, where each variable ranges over a domain and a configuration (solution) to all the variables should satisfy all of the constraints. A fundamental question in the study of random CSPs is the average-case computational complexity of solving ensembles of CSPs. Great amount of theoretical and algorithmic work has been devoted to establish and locate the satisfiability threshold, and studies show that complexity attains the maximum at the SAT-UNSAT transition. Many of the studied CSP models (such as random k-SAT, graph coloring) have fixed domain size, constraint length, and the number of constraints is linear compared with the number of variables. In recent years, a lot of attention has been paid to the study of CSPs with growing domains or constraint length ([13, 7, 4, 5]).

We study constraint satisfaction problems on the so-called planted random ensemble. We show that for a certain class of problems, e.g. We study the structural phase transitions, and the easy/hard/easy pattern in the average computational complexity. We also discuss the finite temperature phase diagram, finding a close connection with the liquid/glass/solid phenomenology. Constraint satisfaction problems (CSPs) stand at the root of the theory of computational complexity [1] and arise in computer science, physics, engineering and many other fields of science.

In this paper we propose a new type of random CSP model, called Model RB, which is a revision to the standard Model B. It is proved that phase transitions from a region where almost all problems are satisfiable to a region where almost all problems are unsatisfiable do exist for Model RB as the number of variables approaches infinity. Moreover, the critical values at which the phase transitions occur are also known exactly. By relating the hardness of Model RB to Model B, it is shown that there exist a lot of hard instances in Model RB.